Section: New Results

Subdomain decomposition

Participants : Astrid Casadei, François Pellegrini, Pierre Ramet [Corresponding member] .

This work aims at finding subdomain decompositions that balance the sizes of off-diagonal contribution blocks.

In terms of graph partitioning, we have expressed this problem as a multi-constraint partitioning problem. In addition to bearing a weight that expresses the workload associated with its degrees of freedom, every graph vertex bears a second weight that holds the number of unknowns to which it is linked outside of its subdomain. Hence, in the nested dissection process, every time a separator is computed, this second weight is updated for each frontier vertex of the separated parts, before they are also recursively separated.

This year, we have set-up a software testbed for experimenting this approach. The Scotch sparse matrix ordering library has been modified so that graph vertices can bear multiple vertex weights. This required a slight change in the interfaces, but also modifications of the internal handling of graphs in many modules (nested dissection, graph coarsening, etc).